package leetcode.linklist;
//给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
//第一直觉:插入排序，超时
//将链表断开，合并两个链表，断开......，归并分治思想
//对于链表如果有四个节点，分为两个链表，两组链表各自两个，再次分开
//分到不可分，合
public class A148 {
     public class ListNode {
         int val;
     ListNode next;
     ListNode() {}
         ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     }

    class Solution {
        public ListNode sortList1(ListNode head) {
            if(head==null||head.next==null)return head;
            ListNode dummy=new ListNode(0,head);
            ListNode link=head.next;
            head.next=null;
            ListNode p=link;
            while(p!=null){
                ListNode next=p.next;
                ListNode q=dummy;
                //如果q的下一个节点比p大，那么p接在q后面
                while(q.next!=null&&q.next.val<=p.val){
                    q=q.next;
                }
                //找到了插入位置
                p.next=q.next;
                q.next=p;
                p=next;
            }
            return dummy.next;
        }

        public ListNode sortList(ListNode head){
        if(head==null||head.next==null)return head;
            //找到中间节点截成两半
            ListNode head2=midNode(head);
            //并且返回第二条链表的头节点
            //归并排序
            //先分治
            head=sortList(head);
            head2=sortList(head2);
            //此时两条链表各种有序
            //排序
            return mergeSort(head,head2);
        }

        private ListNode mergeSort(ListNode head1, ListNode head2) {
            ListNode node1=head1;
            ListNode node2=head2;
            ListNode dummy=new ListNode(0,null);
            ListNode p=dummy;
            //当两条链表均不为空
            while(node1!=null&&node2!=null){
                //拿到较小的节点
                if(node1.val<=node2.val){

                    p.next=node1;

                    node1=node1.next;
                }else{
                    p.next=node2;

                    node2=node2.next;
                }
                p=p.next;
            }
            //如果此时有一条链表空，另一个没空，则直接接到后面
            if(node1!=null){
                p.next=node1;
            }else if(node2!=null){
                p.next=node2;
            }




            return dummy.next;
        }

        private ListNode midNode(ListNode head) {
            ListNode slow=head;
            ListNode fast=head;
            ListNode pre=head;
        while(fast!=null&&fast.next!=null){
            //记录slow的前驱节点，用于后续断开连接
            pre=slow;
            slow=slow.next;
            fast=fast.next;
        }
        //断开连接
            pre.next=null;
        return slow;//slow作为第二条链表的头节点，返回
        }


    }
}
